
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1798. -- [Ahoi2009]Seq 维护序列seq
</title><center><h2>1798: [Ahoi2009]Seq 维护序列seq
</h2><span class=green>Time Limit: </span>30 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>590&nbsp;&nbsp;<span class=green>Solved: </span>245<br>[<a href='submitpage.php?id=1798'>Submit</a>][<a href='problemstatus.php?id=1798'>Status</a>][<a href='bbs.php?id=1798'>Discuss</a>]</center><h2>Description</h2><div class=content>    老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。
    有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式：
(1)把数列中的一段数全部乘一个值;
(2)把数列中的一段数全部加一个值;
(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。

</div><h2>Input</h2><div class=content>第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式：
操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。
操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。
操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值
(1≤t≤g≤N)。
       同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

</div><h2>Output</h2><div class=content>    对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>7 43<br />
1 2 3 4 5 6 7<br />
5<br />
1 2 5 5<br />
3 2 4<br />
2 3 7 9<br />
3 1 3<br />
3 4 7<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>2<br />
35<br />
8<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p>【样例说明】<br />
<br />
初始时数列为(1,2,3,4,5,6,7)。<br />
经过第1次操作后，数列为(1,10,15,20,25,6,7)。<br />
对第2次操作，和为10+15+20=45，模43的结果是2。<br />
经过第3次操作后，数列为(1,10,24,29,34,15,16}<br />
对第4次操作，和为1+10+24=35，模43的结果是35。<br />
对第5次操作，和为29+34+15+16=94,模43的结果是8。<br />
<br />
<br />
<br />
测试数据规模如下表所示<br />
<br />
数据编号	1	2	3	4	5	6	7	8	9	10<br />
N=	10	1000	1000	10000	60000	70000	80000	90000	100000	100000<br />
M=	10	1000	1000	10000	60000	70000	80000	90000	100000	100000<br />
</p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Day1'>Day1</a></p></div><center>[<a href='submitpage.php?id=1798'>Submit</a>][<a href='problemstatus.php?id=1798'>Status</a>][<a href='bbs.php?id=1798'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
